package other;

import java.util.HashMap;

/**
 * 递归
 * @author Tang Jiujia
 * @since 14:11 2020-04-08
 */
public class Recursion {

    private static HashMap<Long, Long> solvedMap = new HashMap<>();

    /**
     * 计算台阶走法数量
     *
     * @param count	台阶数
     * @return int
     */
    private static long goStepMethod(long count) {
        //终止条件
        if (count == 1) {
            return 1;
        }
        if (count == 2) {
            return 2;
        }
        if (solvedMap.containsKey(count)) {
            return solvedMap.get(count);
        }
        long result = goStepMethod(count - 1) + goStepMethod(count - 2);
        solvedMap.put(count, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(goStepMethod(50));
    }
}
